package com.zyk.leetcode;

import com.zyk.util.ListUtil;

/**
 * @author zhangsan
 * @date 2021/4/25 23:24
 */
public class C19 {

    // 反转删除
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        head = reverseList(head);
        if (n == 1) return reverseList(head.next);
        ListNode cur = head;
        ListNode pre = null;
        for (int i = 1; i < n; i++) {
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        return reverseList(head);
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 一次遍历, 快慢指针, 快指针先走n步, 慢指针和快指针一起走, 慢指针到终点, 快指针就是要删除的那一个
    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode slow = head, fast = head;
        for (int i = 1; i < n; i++)
            fast = fast.next;
        fast = fast.next;
        if(fast == null) return slow.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2};
        ListNode head = ListUtil.generateList(arr);
        int n = 1;
        head = removeNthFromEnd2(head, n);
//        head = reverseList(head);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

}
